/**
 * 定义一个泛型接口Node，用于表示链表中的节点
 */
type Node<T> = {
  /**
   * #### 节点的值
   */
  value: T;
  /**
   * #### 下一个节点的引用
   */
  next?: Node<T>;
  /**
   * #### 上一个节点的引用
   */
  prev?: Node<T>;
};

/**
 * #### 创建一个节点
 * @param value 节点的值
 * @returns
 */
function createNode<T>(value: T) {
  return {
    value,
  } as Node<T>;
}

/**
 * ### LRU缓存实现
 * @author Zhentiw
 * @date 2025-4-8
 * @see https://www.cnblogs.com/Answer1215/p/17655901.html
 * @description LRU（Least Recently Used）缓存是一种缓存淘汰策略，它根据数据的使用频率来决定数据的存储和淘汰。LRU缓存会优先淘汰最近最少使用的数据，以保证缓存中的数据都是最近使用过的。
 */
class LRU<K, V> {
  // 定义缓存长度
  private length: number;
  private capacity: number;
  private head?: Node<V>;
  private tail?: Node<V>;
  private lookup: Map<K, Node<V>>;
  private reverseLookup: Map<Node<V>, K>;

  /**
   * ### LRU缓存构造函数
   * @param capacity 缓存容量,默认为10
   */
  constructor(capacity: number = 10) {
    // 初始化缓存容量
    this.capacity = capacity;
    this.length = 0;
    this.tail = this.head = void 0;
    this.lookup = new Map<K, Node<V>>();
    this.reverseLookup = new Map<Node<V>, K>();
  }

  /**
   * #### 更新缓存
   * @param key 缓存的键
   * @param value 缓存的值
   */
  update(key: K, value: V) {
    // 更新缓存
    let node = this.lookup.get(key);
    if (!node) {
      // 如果缓存中不存在该键，则创建新节点
      node = createNode(value);
      this.length++;
      this.prepend(node);
      this.trimCache();
      this.lookup.set(key, node);
      this.reverseLookup.set(node, key);
    } else {
      // 如果缓存中存在该键，则更新节点值
      this.detach(node);
      this.prepend(node);
      node.value = value;
    }
  }

  /**
   * #### 获取缓存中的值
   * @param key 缓存的键
   * @returns 缓存的值
   */
  get(key: K) {
    // 获取缓存中的值
    const node = this.lookup.get(key);
    if (!node) {
      return void 0;
    }
    this.detach(node);
    this.prepend(node);
    return node.value;
  }

  /**
   * #### 添加到链表头部的方法
   * @param node 要添加到链表头部的节点
   */
  private prepend(node: Node<V>) {
    // 将节点添加到链表头部
    if (!this.head) {
      // 如果链表为空，将节点同时设置为头节点和尾节点
      this.head = this.tail = node;
    } else {
      // 如果链表不为空，将节点设置为头节点，并将原头节点的prev指针指向新节点
      node.next = this.head;
      this.head.prev = node;
      this.head = node;
    }
  }

  /**
   * #### 移除指定的节点
   * @param node 要移除的节点
   */
  private detach(node: Node<V>) {
    // 将节点从链表中移除
    if (node.prev) {
      // 如果节点有前驱节点，则将前驱节点的next指针指向当前节点的next节点
      node.prev.next = node.next;
    }
    if (node.next) {
      // 如果节点有后继节点，则将后继节点的prev指针指向当前节点的prev节点
      node.next.prev = node.prev;
    }
    if (this.head === node) {
      // 如果当前节点是头节点，则将头节点指向当前节点的next节点
      this.head = this.head.next;
    }
    if (this.tail === node) {
      // 如果当前节点是尾节点，则将尾节点指向当前节点的prev节点
      this.tail = this.tail.prev;
    }
    node.next = void 0;
    node.prev = void 0;
  }

  /**
   * #### 当缓存长度超过指定的容量时移除缓存尾部节点
   * @private
   * @returns
   */
  private trimCache() {
    if (this.length <= this.capacity) {
      return;
    }
    // 获取尾部节点
    const tail = this.tail;
    // 将尾部节点从链表中移除
    this.detach(tail!);
    // 获取尾部节点的key
    const key = this.reverseLookup.get(tail!);
    // 从lookup中删除尾部节点的key
    this.lookup.delete(key!);
    // 从reverseLookup中删除尾部节点的key
    this.reverseLookup.delete(tail!);
    // 缓存长度减一
    this.length--;
  }
}

export default LRU;
